//You are given n balloons, indexed from 0 to n - 1. Each balloon is painted 
//with a number on it represented by an array nums. You are asked to burst all the 
//balloons. 
//
// If you burst the iᵗʰ balloon, you will get nums[i - 1] * nums[i] * nums[i + 1
//] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if 
//there is a balloon with a 1 painted on it. 
//
// Return the maximum coins you can collect by bursting the balloons wisely. 
//
// 
// Example 1: 
//
// 
//Input: nums = [3,1,5,8]
//Output: 167
//Explanation:
//nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
//coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167 
//
// Example 2: 
//
// 
//Input: nums = [1,5]
//Output: 10
// 
//
// 
// Constraints: 
//
// 
// n == nums.length 
// 1 <= n <= 500 
// 0 <= nums[i] <= 100 
// 
// Related Topics 数组 动态规划 👍 828 👎 0

package leetcode.editor.cn;

public class P312BurstBalloons {
    public static void main(String[] args) {
        Solution solution = new P312BurstBalloons().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        int maxCoins(int[] nums) {
            int n = nums.length;
            // 添加两侧的虚拟气球
            int[] points = new int[n + 2];
            points[0] = points[n + 1] = 1;
            for (int i = 1; i <= n; i++) {
                points[i] = nums[i - 1];
            }        // base case 已经都被初始化为 0
            int[][] dp = new int[n + 2][n + 2];
            // 开始状态转移
            // i 应该从下往上
            for (int i = n; i >= 0; i--) {
                // j 应该从左往右
                for (int j = i + 1; j < n + 2; j++) {
                    // 最后戳破的气球是哪个？
                    for (int k = i + 1; k < j; k++) {
                        // 择优做选择
                        dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + points[i] * points[j] * points[k]);
                    }
                }
            }
            return dp[0][n + 1];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}